#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
namespace STL
{
    template <class key, class val>
    class AvlTreeNode
    {
    public:
        std::pair<key, val> _data;
        AvlTreeNode *_parent;
        AvlTreeNode *_leftchild;
        AvlTreeNode *_rightchild;
        int _bf;

        AvlTreeNode(const std::pair<key, val> &data)
            : _data(data), _parent(nullptr), _leftchild(nullptr), _rightchild(nullptr), _bf(0)
        {
        }
    };

    template <class key, class val>
    class AvlTree
    {
        using TreeNode = AvlTreeNode<key, val>;

    public:
        AvlTree()
            : _root(nullptr)
        {
        }

    public:
        bool insert(const std::pair<key, val> &in)
        {
            // 1、找到合适插入的结点位置
            TreeNode *parent = nullptr;
            TreeNode *cur = _root;
            while (cur)
            {
                TreeNode *lchild = cur->_leftchild;
                TreeNode *rchild = cur->_rightchild;
                if (cur->_data.first < in.first)
                {
                    parent = cur;
                    cur = rchild;
                }
                else if (cur->_data.first > in.first)
                {
                    parent = cur;
                    cur = lchild;
                }
                else
                {
                    break;
                }
            }

            if (parent == nullptr)
            {
                _root = new TreeNode(in);
                return true;
            }
            cur = new TreeNode(in);
            cur->_parent = parent;
            if (parent->_data.first < in.first)
            {
                // 插入右边
                parent->_rightchild = cur;
            }
            else
            {
                // 插入左边
                parent->_leftchild = cur;
            }

            while (parent)
            {
                if (cur == parent->_leftchild)
                {
                    parent->_bf -= 1;
                }
                else
                {
                    parent->_bf += 1;
                }

                if (parent->_bf == 1 || parent->_bf == -1)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
                else if (parent->_bf == 0)
                {
                    break;
                }
                else if (parent->_bf == 2 || parent->_bf == -2)
                {
                    // 旋转
                    if (parent->_bf == -2 && cur->_bf == -1)
                    {
                        rotateR(parent);
                    }
                    else if (parent->_bf == 2 && cur->_bf == 1)
                    {
                        rotateL(parent);
                    }
                    else if (parent->_bf == -2 && cur->_bf == 1)
                    {
                        rotateLR(parent);
                    }
                    else if (parent->_bf == 2 && cur->_bf == -1)
                    {
                        rotateRL(parent);
                    }
                    else
                    {
                        assert(false);
                    }
                    break;
                }
                else
                {
                    assert(false);
                }
            }
            return true;
        }

        // 按层打印 + 中序打印（调试用）
        void print() const
        {
            if (!_root)
            {
                std::cout << "空树\n";
                return;
            }
            _layerPrint();
            inorder();
            fflush(stdout);
        }

        void inorder() const
        {
            std::cout << "中序：";
            _inorder(_root);
            std::cout << "\n";
        }

        void _inorder(TreeNode *node) const
        {
            if (!node)
                return;
            _inorder(node->_leftchild);
            std::cout << "{" << node->_data.first << "," << node->_data.second << "} ";
            _inorder(node->_rightchild);
        }

        void _layerPrint() const
        {
            std::vector<TreeNode *> cur, nxt;
            cur.push_back(_root);
            for (int depth = 0; !cur.empty(); ++depth)
            {
                std::cout << "Layer " << depth << " : ";
                for (auto *p : cur)
                {
                    std::cout << p->_data.first << " ";
                    if (p->_leftchild)
                        nxt.push_back(p->_leftchild);
                    if (p->_rightchild)
                        nxt.push_back(p->_rightchild);
                }
                std::cout << '\n';
                cur.swap(nxt);
                nxt.clear();
            }
        }

    private:
        void rotateL(TreeNode *parent)
        {
            TreeNode *grandparent = parent->_parent;
            TreeNode *rchild = parent->_rightchild;
            TreeNode *rlchild = rchild->_leftchild;
            // 1、锁定rlchild
            parent->_rightchild = rlchild;
            if (rlchild)
                rlchild->_parent = parent;
            // 2、锁定parent
            rchild->_leftchild = parent;
            parent->_parent = rchild;
            // 3、锁定rchild
            if (grandparent == nullptr)
            {
                rchild->_parent = nullptr;
                _root = rchild;
            }
            else
            {
                if (grandparent->_rightchild == parent)
                {
                    grandparent->_rightchild = rchild;
                }
                else if (grandparent->_leftchild == parent)
                {
                    grandparent->_leftchild = rchild;
                }
                else
                {
                    assert(false);
                }
                rchild->_parent = grandparent;
            }

            // 4、更新平衡因子
            parent->_bf = rchild->_bf = 0;
        }

        void rotateR(TreeNode *parent)
        {
            TreeNode *grandparent = parent->_parent;
            TreeNode *lchild = parent->_leftchild;
            TreeNode *lrchild = lchild->_rightchild;
            // 1、锁定lrchild
            parent->_leftchild = lrchild;
            if (lrchild)
                lrchild->_parent = parent;
            // 2、锁定parent
            lchild->_rightchild = parent;
            parent->_parent = lchild;
            // 3、锁定lchild
            if (grandparent == nullptr)
            {
                lchild->_parent = nullptr;
                _root = lchild;
            }
            else
            {
                if (grandparent->_rightchild == parent)
                {
                    grandparent->_rightchild = lchild;
                }
                else if (grandparent->_leftchild == parent)
                {
                    grandparent->_leftchild = lchild;
                }
                else
                {
                    assert(false);
                }
                lchild->_parent = grandparent;
            }
            // 4、更新平衡因子
            lchild->_bf = parent->_bf = 0;
        }

        void rotateLR(TreeNode *parent)
        {
            TreeNode *lchild = parent->_leftchild;
            TreeNode *lrchild = lchild->_rightchild;

            rotateL(lchild);
            rotateR(parent);

            if (lrchild->_bf == 0)
            {
                lchild->_bf = 0;
                lrchild->_bf = 0;
                parent->_bf = 0;
            }
            else if (lrchild->_bf == 1)
            {
                lchild->_bf = -1;
                lrchild->_bf = 0;
                parent->_bf = 0;
            }
            else if (lrchild->_bf == -1)
            {
                lchild->_bf = 0;
                lrchild->_bf = 0;
                parent->_bf = 1;
            }
            else
            {
                assert(false);
            }
        }

        void rotateRL(TreeNode *parent)
        {
            TreeNode *rchild = parent->_rightchild;
            TreeNode *rlchild = rchild->_leftchild;

            rotateR(parent->_rightchild);
            rotateL(parent);

            if (rlchild->_bf == 0)
            {
                parent->_bf = 0;
                rchild->_bf = 0;
                rlchild->_bf = 0;
            }
            else if (rlchild->_bf == 1)
            {
                parent->_bf = -1;
                rchild->_bf = 0;
                rlchild->_bf = 0;
            }
            else if (rlchild->_bf == -1)
            {
                parent->_bf = 0;
                rchild->_bf = 1;
                rlchild->_bf = 0;
            }
            else
            {
                assert(false);
            }
        }

    private:
        TreeNode *_root;
    };
}